/*
 * @lc app=leetcode.cn id=684 lang=cpp
 *
 * [684] 冗余连接
 *
 * https://leetcode.cn/problems/redundant-connection/description/
 *
 * algorithms
 * Medium (67.20%)
 * Likes:    480
 * Dislikes: 0
 * Total Accepted:    77.4K
 * Total Submissions: 115.2K
 * Testcase Example:  '[[1,2],[1,3],[2,3]]'
 *
 * 树可以看成是一个连通且 无环 的 无向 图。
 *
 * 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n
 * 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai
 * 和 bi 之间存在一条边。
 *
 * 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n
 * 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 *
 * 输入: edges = [[1,2], [1,3], [2,3]]
 * 输出: [2,3]
 *
 *
 * 示例 2：
 *
 *
 *
 *
 * 输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
 * 输出: [1,4]
 *
 *
 *
 *
 * 提示:
 *
 *
 * n == edges.length
 * 3
 * edges[i].length == 2
 * 1
 * ai != bi
 * edges 中无重复元素
 * 给定的图是连通的 
 *
 *
 */

// @lc code=start
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
// 并查集
class UnionFind {
    vector<int> father;
    vector<int> rank;

public:
    UnionFind(int n) : father(n), rank(n, 1) {
        // iota函数可以在迭代器范围内填充从第三个参数起的递增序列
        iota(father.begin(), father.end(), 0);
    }

    int find(int p) {
        while (p != father[p]) {
            // 路径压缩，使得下次查找更快
            father[p] = father[father[p]];
            p = father[p];
        }
        return p;
    }

    void connect(int p, int q) {
        int i = find(p), j = find(q);
        if (i != j) {
            // 按秩归并：每次合并都把深度较小的集合合并在深度较大的集合下面
            if (rank[i] < rank[j]) {
                father[i] = j;
                rank[j] += rank[i];
            }
            else {
                father[j] = i;
                rank[i] += rank[j];
            }
        }
    }

    bool isConnected(int p, int q) {
        return find(p) == find(q);
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>> &edges) {
        int n = edges.size();
        UnionFind uf(n + 1);
        for (auto edge : edges) {
            int u = edge[0], v = edge[1];
            if (uf.isConnected(u, v)) {
                return edge;
            }
            uf.connect(u, v);
        }
        return vector<int>{-1, -1};
    }
};
// @lc code=end
